//
//  BC_Board.m
//  CocOth
//
//  Created by BrunoCausse on 06/11/10.
//  Copyright 2010-2013 poulailler cie. All rights reserved.
//

#import "BC_Board.h"
#import "BC_Move.h"

#import "BC_Hashtable.h"

#import "BC_Mersenne.h"


static unsigned long long hash_set[BOARD_SIZE][2];
static unsigned long long hash_flip[BOARD_SIZE];
static unsigned long long hash_swap;


void init_hashconst() {
    
    unsigned long long init[4]={0x12345ULL, 0x23456ULL, 0x34567ULL, 0x45678ULL}, length=4;
    init_by_array64(init, length);
    
    hash_swap = genrand64_int64();
    
    for(int i = 0; i<BOARD_SIZE; i++) {
        hash_set[i][BLACK] = genrand64_int64() ^ hash_swap;
        hash_set[i][WHITE] = genrand64_int64() ^ hash_swap;
        
        hash_flip[i] =  hash_set[i][BLACK] ^  hash_set[i][WHITE];
    }
    
}




/*! macros to check if a move (<= 6 flips) is correct along a direction */
#define BOARD_CHECK_MOVE_6(dir)             \
( sq[dir] == o &&                           \
( sq[2 * dir] == p || (sq[2 * dir] == o &&  \
( sq[3 * dir] == p || (sq[3 * dir] == o &&  \
( sq[4 * dir] == p || (sq[4 * dir] == o &&  \
( sq[5 * dir] == p || (sq[5 * dir] == o &&  \
( sq[6 * dir] == p || (sq[6 * dir] == o &&  \
sq[7 * dir] == p)))))))))))

/*! macros to check if a move (<= 4 flips) is correct along a direction */
#define BOARD_CHECK_MOVE_4(dir)             \
( sq[dir] == o &&                           \
( sq[2 * dir] == p || (sq[2 * dir] == o &&  \
( sq[3 * dir] == p || (sq[3 * dir] == o &&  \
( sq[4 * dir] == p || (sq[4 * dir] == o &&  \
sq[5 * dir] == p)))))))


/*! macro to get a move along a direction */
#define BOARD_GET_MOVE(dir, max_flip)                  \
if (BOARD_CHECK_MOVE_##max_flip(dir)) {                \
int z = pos + (dir);                                   \
do {											       \
[move setPosition:z atIndex:[move increment_nFlips]];  \
[move XORHashcode:hash_flip[z]];                       \
z += (dir);                                            \
} while (square[z] == o);                              \
}

/*! macro to swap colors */
#define OPPONENT(p) ((p) ^ 1)

/*! a flipping direction ID for each square */
const int FLIPPING_DIRECTION_ID[BOARD_SIZE] = {
	0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 1, 1, 2, 2, 2, 2, 3, 3,
	0, 1, 1, 2, 2, 2, 2, 3, 3,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 4, 4, 5, 5, 5, 5, 6, 6,
	0, 7, 7, 8, 8, 8, 8, 9, 9,
	0, 7, 7, 8, 8, 8, 8, 9, 9,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

NSInteger firstNumSort(BC_Move *move1, BC_Move *move2, void *context) {
		
    if ([move1 score] < [move2 score])
        return NSOrderedAscending;
    else if ([move1 score] > [move2 score])
        return NSOrderedDescending;
	
    return NSOrderedSame;
}


@implementation BC_Board

@synthesize player;
@synthesize n_empties;
@synthesize hashcode;


- (id)init
{
	return [self initWithString:@"[-------- -------- -------- ---OX--- ---XO--- -------- -------- -------- X]"];
}


//TODO gestion des othellier incorrect
- (id)initWithString:(NSString *)boardString
{
	
	const int presorted_position[] = {
		A1, A8, H1, H8,                    /* Corner */
		A3, A6, C1, C8, F1, F8, H3, H6,    /* A */
		C3, C6, F3, F6,                    /* D */
		A4, A5, D1, D8, E1, E8, H4, H5,    /* B */
		C4, C5, D3, D6, E3, E6, F4, F5,    /* E */
		B4, B5, D2, D7, E2, E7, G4, G5,    /* G */
		B3, B6, C2, C7, F2, F7, G3, G6,    /* F */
		A2, A7, B1, B8, G1, G8, H2, H7,    /* C */
		B2, B7, G2, G7,                    /* X */
	};
	
//	NSError *error = [NSError errorWithDomain:@"incorrect board String" 
//										 code:-1 
//									 userInfo:nil];
	
	self = [super init]; //utile avec NSObject?
	if (self) {
		
		NSString *lowerCaseBoardString = [boardString lowercaseString];
		
		for(int i = 0; i<BOARD_SIZE; i++)
			square[i] = OFF_SIDE;
		
		player = OFF_SIDE;
		
		n_discs[BLACK] = n_discs[WHITE] = n_empties = 0;
		
		int id = 0;
		for(int i = A1; i <= H8; i+=9) {
			for(int j = i; j < (i+8); j++) {
				switch([lowerCaseBoardString characterAtIndex:id]) {
					case 'b':
					case 'x':
					case '*':
						square[j] = BLACK;
						n_discs[BLACK]++;
						break;
					case 'o':
					case 'w':
						square[j] = WHITE;
						n_discs[WHITE]++;
						break;
					case '-':
					case '.':
						square[j] = EMPTY;
						n_empties++;
						break;
					case ' ':
					case '[':
						j--;
						break;
					default :
						//error
						[self release];
						
						[[NSException exceptionWithName:@"init failure" 
												 reason:@"incorrect board String" 
											   userInfo:nil] raise];
						//pour la forme inutile
						break;
						
				}
				id++;
			}
		}
		
		for(; id < [lowerCaseBoardString length] && player == OFF_SIDE; id++) {
			switch([lowerCaseBoardString characterAtIndex:id]) {
				case 'b':
				case 'x':
				case '*':
					player = BLACK;
					break;
				case 'o':
				case 'w':
					player = WHITE;
					break;
			}
		}
		
		//gestion de l'echec
		if (player == OFF_SIDE) {
			
			[self release];

			[[NSException exceptionWithName:@"init failure" 
									 reason:@"incorrect board String" 
								   userInfo:nil] raise];
			
			//inutile
			return nil;
			
		}
		
		//init empties
		SquareList *empty = empties;
		empty->position = NOMOVE; /* sentinel */
		empty->previous = NULL;
		empty->next = empty + 1;
		empty = empty->next;
		for (int i = 0; i < 60; i++) {    /* add empty squares */
			if (square[presorted_position[i]] == EMPTY) {
				empty->position = presorted_position[i];
				empty->previous = empty - 1;
				empty->next = empty + 1;
				position_to_empties[presorted_position[i]] = empty;
				empty = empty->next;
			}
		}
		empty->position = NOMOVE; /* sentinel */
		empty->previous = empties - 1;
		empty->next = NULL;
		
        /* set hash_code */
        hashcode = 0;
        if((player == WHITE) ^ ((n_empties & 1) == 1)){
            hashcode ^= hash_swap;
        }
        for(int i = A1; i <= H8; i += 9) {
            for(int j = i; j < i + 8; j++){
                if(square[j] != EMPTY) {
                    hashcode ^= hash_set[j][square[j]];
                }
            }
        }
        					
	}
	
	return self;
	
	
}

- (id)copyWithZone:(NSZone *)zone
{
	BC_Board *copy = [[[self class] allocWithZone: zone]
					  initWithString:[self descriptionForScript]];
    return copy;
}

- (BOOL)isLegal:(int)pos {
	
	const char p = player;
	const char o = OPPONENT(p);
	
	const char *sq  = square + pos;
	
	if (square[pos] == EMPTY) {
		
		switch (FLIPPING_DIRECTION_ID[pos]) {
			case 1:
				return  (BOARD_CHECK_MOVE_6(SE) ||
						 BOARD_CHECK_MOVE_6(S ) ||
						 BOARD_CHECK_MOVE_6( E));
			case 3:
				return  (BOARD_CHECK_MOVE_6(SW) ||
						 BOARD_CHECK_MOVE_6( W) ||
						 BOARD_CHECK_MOVE_6(S ));
			case 7:
				return  (BOARD_CHECK_MOVE_6(NE) ||
						 BOARD_CHECK_MOVE_6(N ) ||
						 BOARD_CHECK_MOVE_6( E));
			case 9:
				return  (BOARD_CHECK_MOVE_6(NW) ||
						 BOARD_CHECK_MOVE_6(N ) ||
						 BOARD_CHECK_MOVE_6( W));
			case 2:
				return  (BOARD_CHECK_MOVE_6(S ) ||
						 BOARD_CHECK_MOVE_4(SE) ||
						 BOARD_CHECK_MOVE_4(SW) ||
						 BOARD_CHECK_MOVE_4( E) ||
						 BOARD_CHECK_MOVE_4( W));
			case 4:
				return  (BOARD_CHECK_MOVE_6( E) ||
						 BOARD_CHECK_MOVE_4(NE) ||
						 BOARD_CHECK_MOVE_4(SE) ||
						 BOARD_CHECK_MOVE_4(N ) ||
						 BOARD_CHECK_MOVE_4(S ));
			case 6:
				return  (BOARD_CHECK_MOVE_6( W) ||
						 BOARD_CHECK_MOVE_4(NW) ||
						 BOARD_CHECK_MOVE_4(SW) ||
						 BOARD_CHECK_MOVE_4(S ) ||
						 BOARD_CHECK_MOVE_4(N ));
			case 8:
				return  (BOARD_CHECK_MOVE_6(N ) ||
						 BOARD_CHECK_MOVE_4(NE) ||
						 BOARD_CHECK_MOVE_4(NW) ||
						 BOARD_CHECK_MOVE_4( E) ||
						 BOARD_CHECK_MOVE_4( W));
			case 5:
				return  (BOARD_CHECK_MOVE_4(N ) ||
						 BOARD_CHECK_MOVE_4( E) ||
						 BOARD_CHECK_MOVE_4(S ) ||
						 BOARD_CHECK_MOVE_4( W) ||
						 BOARD_CHECK_MOVE_4(NE) ||
						 BOARD_CHECK_MOVE_4(SE) ||
						 BOARD_CHECK_MOVE_4(NW) ||
						 BOARD_CHECK_MOVE_4(SW));
		}
	}
	
	
	return NO;	
	
}


- (int)generateMove:(BC_Move *)move
{
	const char p = player;
	const char o = OPPONENT(p);
	
	int pos = [move positionAtIndex:0];
	
	const char *sq  = square + pos;
	[move setNFlips:0];
    
    [move setHashcode:hash_set[pos][player]];

	
	if (square[pos] == EMPTY) {

		switch (FLIPPING_DIRECTION_ID[pos]) {
			case 1:
				BOARD_GET_MOVE( E, 6);
				BOARD_GET_MOVE(S , 6);
				BOARD_GET_MOVE(SE, 6);
				break;
			case 3:
				BOARD_GET_MOVE( W, 6);
				BOARD_GET_MOVE(SW, 6);
				BOARD_GET_MOVE(S , 6);
				break;
			case 7:
				BOARD_GET_MOVE(N , 6);
				BOARD_GET_MOVE(NE, 6);
				BOARD_GET_MOVE( E, 6);
				break;
			case 9:
				BOARD_GET_MOVE(NW, 6);
				BOARD_GET_MOVE(N , 6);
				BOARD_GET_MOVE( W, 6);
				break;
			case 2:
				BOARD_GET_MOVE( W, 4);
				BOARD_GET_MOVE( E, 4);
				BOARD_GET_MOVE(SW, 4);
				BOARD_GET_MOVE(S , 6);
				BOARD_GET_MOVE(SE, 4);
				break;
			case 4:
				BOARD_GET_MOVE(N , 4);
				BOARD_GET_MOVE(NE, 4);
				BOARD_GET_MOVE( E, 6);
				BOARD_GET_MOVE(S , 4);
				BOARD_GET_MOVE(SE, 4);
				break;
			case 6:
				BOARD_GET_MOVE(NW, 4);
				BOARD_GET_MOVE(N , 4);
				BOARD_GET_MOVE( W, 6);
				BOARD_GET_MOVE(SW, 4);
				BOARD_GET_MOVE(S , 4);
				break;
			case 8:
				BOARD_GET_MOVE(NW, 4);
				BOARD_GET_MOVE(N , 6);
				BOARD_GET_MOVE(NE, 4);
				BOARD_GET_MOVE( W, 4);
				BOARD_GET_MOVE( E, 4);
				break;
			case 5:
				BOARD_GET_MOVE(NW, 4);
				BOARD_GET_MOVE(N , 4);
				BOARD_GET_MOVE(NE, 4);
				BOARD_GET_MOVE( W, 4);
				BOARD_GET_MOVE( E, 4);
				BOARD_GET_MOVE(SW, 4);
				BOARD_GET_MOVE(S , 4);
				BOARD_GET_MOVE(SE, 4);
				break;
		}
	}
		
	return [move nFlips];
}

- (void)doMove:(BC_Move *)move
{
	if([move positionAtIndex: 0] == PASS) {
		[self doPass];
        return;
    }

	const char p = player;
	const char o = OPPONENT(p);

	switch([move nFlips]) {
		case 18: square[[move positionAtIndex:18]] = p;
		case 17: square[[move positionAtIndex:17]] = p;
		case 16: square[[move positionAtIndex:16]] = p;
		case 15: square[[move positionAtIndex:15]] = p;
		case 14: square[[move positionAtIndex:14]] = p;
		case 13: square[[move positionAtIndex:13]] = p;
		case 12: square[[move positionAtIndex:12]] = p;
		case 11: square[[move positionAtIndex:11]] = p;
		case 10: square[[move positionAtIndex:10]] = p;
		case  9: square[[move positionAtIndex: 9]] = p;
		case  8: square[[move positionAtIndex: 8]] = p;
		case  7: square[[move positionAtIndex: 7]] = p;
		case  6: square[[move positionAtIndex: 6]] = p;
		case  5: square[[move positionAtIndex: 5]] = p;
		case  4: square[[move positionAtIndex: 4]] = p;
		case  3: square[[move positionAtIndex: 3]] = p;
		case  2: square[[move positionAtIndex: 2]] = p;
		case  1: square[[move positionAtIndex: 1]] = p;
		case  0: square[[move positionAtIndex: 0]] = p;
	} 
    
    hashcode ^= [move hashcode];
		
	player = o;
	
	n_discs[(int)p] += [move nFlips] + 1;
	n_discs[(int)o] -= [move nFlips];
	n_empties--;
	
	SquareList *empty = position_to_empties[[move positionAtIndex:0]];
	empty->previous->next = empty->next;
	empty->next->previous = empty->previous;
}

- (void)undoMove:(BC_Move *)move
{
	if([move positionAtIndex: 0] == PASS) {
		[self doPass];
        return;
    }
	
	const char p = player;
	const char o = OPPONENT(p);
	
	switch([move nFlips]) {
		case 18: square[[move positionAtIndex:18]] = p;
		case 17: square[[move positionAtIndex:17]] = p;
		case 16: square[[move positionAtIndex:16]] = p;
		case 15: square[[move positionAtIndex:15]] = p;
		case 14: square[[move positionAtIndex:14]] = p;
		case 13: square[[move positionAtIndex:13]] = p;
		case 12: square[[move positionAtIndex:12]] = p;
		case 11: square[[move positionAtIndex:11]] = p;
		case 10: square[[move positionAtIndex:10]] = p;
		case  9: square[[move positionAtIndex: 9]] = p;
		case  8: square[[move positionAtIndex: 8]] = p;
		case  7: square[[move positionAtIndex: 7]] = p;
		case  6: square[[move positionAtIndex: 6]] = p;
		case  5: square[[move positionAtIndex: 5]] = p;
		case  4: square[[move positionAtIndex: 4]] = p;
		case  3: square[[move positionAtIndex: 3]] = p;
		case  2: square[[move positionAtIndex: 2]] = p;
		case  1: square[[move positionAtIndex: 1]] = p;
		case  0: square[[move positionAtIndex: 0]] = EMPTY;
	}
    
    hashcode ^= [move hashcode];
	
	player = o;
	
	n_discs[(int)o] -= [move nFlips] + 1;
	n_discs[(int)p] += [move nFlips];
	n_empties++;
	
	SquareList *empty = position_to_empties[[move positionAtIndex:0]];
	empty->previous->next = empty;
	empty->next->previous = empty;
}

- (BOOL)isEndgame {
	
	if ([self shouldPass]) {
		
		[self doPass];
		
		if([self shouldPass]){
		   [self doPass];
			//endgame
		   return YES;
		}
		
		[self doPass];
	}
	
	return NO;
}

- (int)diff_discs
{
	int score = n_discs[player]-n_discs[OPPONENT(player)];
	
	if (score < 0) score -= n_empties;
	else if (score > 0) score += n_empties;
	
	return score;

}

- (BOOL)shouldPass {
	
	for(SquareList *empty = empties->next; empty->position !=NOMOVE; empty = empty->next) {
		if([self isLegal:empty->position]) {
			return NO;
		}
	}
	return YES;
}
	
- (void)doPass {
	player = OPPONENT(player);
    
    hashcode ^= hash_swap;
}
	

- (int)generateAllMoves:(NSMutableArray *)movesArray
{
	
	for(SquareList *empty = empties->next; empty->position !=NOMOVE; empty = empty->next) {
		BC_Move *move = [[BC_Move alloc] initWithLocation:empty->position];
		if([self generateMove:move]) {
			[movesArray addObject:move];
		}
		[move release];
	}
		
	return [movesArray count];
}

- (int)getMobility
{
	int n_moves = 0;
	
	for(SquareList *empty = empties->next; empty->position !=NOMOVE; empty = empty->next) {
		if([self isLegal:empty->position]) {
			n_moves++;
		}
	}
	
	return n_moves;
}
	

- (void)sort_fastfirst:(NSMutableArray *)moves
{
	for(BC_Move *move in moves) {
		
		[self doMove:move];
		move.score = [self getMobility];
		[self undoMove:move];
		
	}

	//tri du tableau
	[moves sortUsingFunction:firstNumSort context:NULL];
	
}



- (int)discAtRow:(int)row column:(int)column
{
	return square[(row+1)*9 + column+1];
}

- (BOOL)isLegalAtRow:(int)row column:(int)column
{
	int sq = (row+1)*9 + column+1;
	
	return [self isLegal:sq];
}

- (BC_Move *)generateMoveAtRow:(int)row column:(int)column
{
	int sq = (row+1)*9 + column+1;
	
	BC_Move *move = [[[BC_Move alloc] initWithLocation:sq] autorelease];
	if([self generateMove:move]) {
		return move;
	}
	
	return nil;
}

//- (BC_Move *)doMoveAtRow:(int)row column:(int)column
//{
//	int sq = (row+1)*9 + column+1;
//	
//	BC_Move *move = [[[BC_Move alloc] initWithLocation:sq] autorelease];
//	if([self generateMove:move]) {
//		[self doMove:move];
//		return move;
//	}
//	
//	return nil;
//}

- (NSString *)descriptionForZoo
{
	NSMutableString *descript = [NSMutableString stringWithCapacity:66];
	
	for(int i = A1; i <= H8; i+=9) {		
		for(int j = i; j < (i+8); j++) {
			if(square[j] == BLACK)
				[descript appendString:@"X"];
			else if(square[j] == WHITE)
				[descript appendString:@"O"];
			else 
				[descript appendString:@"-"];
		}
	}
	
	if(player == BLACK)
		[descript appendString:@"X"];
	else
		[descript appendString:@"O"];
	
	return descript;
}


- (NSString *)descriptionForScript
{
	NSMutableString *descript = [NSMutableString stringWithCapacity:66];
	
	for(int i = A1; i <= H8; i+=9) {		
		for(int j = i; j < (i+8); j++) {
			if(square[j] == BLACK)
				[descript appendString:@"X"];
			else if(square[j] == WHITE)
				[descript appendString:@"O"];
			else 
				[descript appendString:@"-"];
		}
	}
	
	if(player == BLACK)
		[descript appendString:@" X\n"];
	else
		[descript appendString:@" O\n"];
	
	return descript;
}
	

- (NSString *)description
{
	NSMutableString *descript = [NSMutableString stringWithCapacity:100];
	
	[descript appendString:@"\n  A B C D E F G H\n"];
	
	int row = 1;
	for(int i = A1; i <= H8; i+=9) {
		NSString *rowString = [NSString stringWithFormat:@"%d ", row++];
		[descript appendString:rowString];
		
		for(int j = i; j < (i+8); j++) {
			if(square[j] == BLACK)
				[descript appendString:@"X "];
			else if(square[j] == WHITE)
				[descript appendString:@"O "];
			else 
				[descript appendString:@"- "];
		}
		
		[descript appendString:@"\n"];
	}
	
	[descript appendString:@"trait : "];
	if(player == BLACK)
		[descript appendString:@"BLACK"];
	else if(player == WHITE)
		[descript appendString:@"WHITE"];
	else
		[descript appendString:@"?????"];

	
	return descript;
}
				 
	
			
		



@end
